\documentclass[utf8]{ctexart}

\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{indentfirst}
\usepackage{gnuplot-lua-tikz}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric, arrows}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{newclude}
\usepackage[perpage]{footmisc}

\graphicspath{ {images/} }
\raggedbottom	% 令页面在垂直方向向顶部对齐
\renewcommand\qedsymbol{QED}
\renewcommand{\figurename}{Figure}
\renewcommand{\proofname}{Proof}
\newcommand{\sign}[1]{\mathrm{sgn}(#1)}
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列

\title{Numerical Analysis Homework \#5}
\author{Yin Wenliang\qquad 3200101893}
\date{}

\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\section{Theoretical questions}
\begin{enumerate}
\item
  % 问题1
  \begin{proof}
    Firstly, it's easy to check that $\mathcal{C}[a,b]$ satisfies
(VSA-1)-(VSA-7) in Definition B.2, hence it's a vector space. Next we
check the condition in Definition B.108.
\begin{align*}
  \text{(IP-1)}&\forall f \in \mathcal{C}[a,b], \\
  \left \langle f,f \right
  \rangle &= \int_{a}^{b} \rho(t)|f(t)|^2\text{d}t \ge 0.
\end{align*}
The last inequality follows from $\rho(t) > 0$.
\begin{align*}
  \text{(IP-2)} \left \langle f,f \right
  \rangle = 0 \Leftrightarrow f(t)\equiv 0 , \forall t \in [a,b].
\end{align*}
The sufficiency is obvious. For the necessity, it's easy to prove by
contradiction.
\begin{align*}
  \text{(IP-3)} &\forall f,g,h \in \mathcal{C}[a,b], \\
  \left \langle f+g,h \right
    \rangle &= \int_{a}^{b} \rho(t)(f(t)+g(t))\overline{h(t)}\text{d}t\\
                &= \int_{a}^{b} \rho(t)f(t)\overline{h(t)}\text{d}t + \int_{a}^{b}
    \rho(t)g(t)\overline{h(t)}\text{d}t\\
  &= \left \langle f,h \right \rangle + \left \langle g,h \right \rangle.
\end{align*}
\begin{align*}
  \text{(IP-4)} &\forall f,g\in \mathcal{C}[a,b], \forall s \in \mathbb{R}, \\
   \left \langle sf,g \right
    \rangle &= \int_{a}^{b} \rho(t)sf(t)\overline{g(t)}\text{d}t\\
                &= s\int_{a}^{b} \rho(t)f(t)\overline{g(t)}\text{d}t \\
  &= s\left \langle f,g \right \rangle.
\end{align*}
\begin{align*}
  \text{(IP-5)} &\forall f,g\in \mathcal{C}[a,b], \\
   \left \langle f,g \right
    \rangle &= \int_{a}^{b} \rho(t)f(t)\overline{g(t)}\text{d}t\\
                &= \overline{\int_{a}^{b} \rho(t)g(t)\overline{f(t)}\text{d}t} \\
  &= \overline{\left \langle g,f \right \rangle},
\end{align*}
where the second step follows from $\rho(t) \in \mathbb{R}$.\par
With (IP-1)-(IP-5), we show that $\mathcal{C}[a,b]$ is indeed an inner
product space. Then naturally $\mathcal{C}[a,b]$ becomes a normed
vector space over $\mathbb{R}$ with respect to
\begin{align*}
  \|u\|_2 = \sqrt{\left \langle u,u  \right \rangle} = (\int_{a}^{b} \rho(t)|u(t)|^2\text{d}t)^{\frac{1}{2}},
\end{align*}
which completes the proof.
  \end{proof}
  
\item
  % 问题2
  \textbf{Solution}\par
  \begin{enumerate}
  \item
    With $T_n = \cos{(n\arccos{x})}$, we have
\begin{align*}
  & \forall m \ne n, \left \langle T_n,T_m  \right \rangle \\
  &= \int_{-1}^{1} \frac{1}{\sqrt{1-x^2}}T_n(x)T_m(x)\text{d}x\\
  &= \int_{-1}^{1}
    \frac{1}{\sqrt{1-x^2}}\cos{(n\arccos{x})}\\
  &\quad \quad \quad \cos{(m\arccos{x})}\text{d}x\\
  &= \int_{0}^{\pi}
    \cos{nt}\cos{mt}\text{d}t\\
  &=\frac{1}{2}\int_{-\pi}^{\pi}
    \cos{nt}\cos{mt}\text{d}t = 0.
\end{align*}
Here the third step is from setting $t = \arccos{x}$, and the last
step from the fact that $\cos{nx}$ and $\cos{mx}$ are orthogonal in
$L_{\rho = 1}^2[-\pi,\pi]$.\\
Similarily,
\begin{align*}
  & \forall n > 0, \left \langle T_n,T_n  \right \rangle \\
  &= \int_{-1}^{1} \frac{1}{\sqrt{1-x^2}}T_n(x)^2\text{d}x\\
  &= \int_{-1}^{1}
    \frac{1}{\sqrt{1-x^2}}\cos^2{(n\arccos{x})}\text{d}x\\
  &= \int_{0}^{\pi}
    \cos^2{(nt)}\text{d}t\\
  &=\frac{\pi}{2}\int_{-\pi}^{\pi}
    (\frac{\cos{nt}}{\sqrt{\pi}})^2\text{d}t = \frac{\pi}{2}.\\
  &\left \langle T_0,T_0  \right \rangle =\int_{-1}^{1} \frac{1}{\sqrt{1-x^2}}\text{d}x = \pi.
\end{align*}
  
\item
  By definition $T_n = \cos{(n\arccos{x})}$, we have
\begin{align*}
  T_0(x) &= 1,\\
  T_1(x) &= x,\\
  T_2(x) &= 2x^2-1,\\
  T_3(x) &= 4x^3-3x.
\end{align*}
By (a), $\forall n > 0$, $\|T_n\|^2 = \frac{\pi}{2}$, and $\|T_0\|^2 = \pi$, hence
\begin{align*}
  u_0^* &= \sqrt{\frac{1}{\pi}},\\
  u_1^* &= \sqrt{\frac{2}{\pi}}x,\\
  u_2^* &= \sqrt{\frac{2}{\pi}}(2x^2-1),\\
  u_3^* &= \sqrt{\frac{2}{\pi}}(4x^3-3x).
\end{align*}
  \end{enumerate}
  
\item
  % 问题3
  \begin{enumerate}
  \item
    With $u_0^*,u_1^*,u_2^*$ in Question 2, we compute that
\begin{align*}
  \left \langle y,u_0^*  \right \rangle &= \int_{-1}^{1}
  \sqrt{\frac{1}{\pi}}\text{d}x = 2\sqrt{\frac{1}{\pi}},\\
  \left \langle y,u_1^*  \right \rangle &= \int_{-1}^{1}
                                          \sqrt{\frac{2}{\pi}}x\text{d}x = 0,\\
  \left \langle y,u_2^*  \right \rangle &= \int_{-1}^{1}
  \sqrt{\frac{2}{\pi}}(2x^2-1)\text{d}x = -\frac{2}{3}\sqrt{\frac{2}{\pi}}.
\end{align*}
Hence
\begin{align*}
  \varphi_2 &=  \left \langle y,u_0^*  \right \rangle u_0^* + \left
  \langle y,u_1^*  \right \rangle u_1^* + \left \langle y,u_2^*
  \right \rangle u_2^*\\
  &= -\frac{2}{3}\sqrt{\frac{2}{\pi}}[\sqrt{\frac{2}{\pi}}(2x^2-1)] +
    2\sqrt{\frac{1}{\pi}}\sqrt{\frac{1}{\pi}}\\
  &= -\frac{8}{3\pi}x^2 + \frac{10}{3\pi}.
\end{align*}
  
\item
  To get normal equation, we compute
\begin{align*}
  \left \langle 1,1  \right \rangle &= \|T_0\|^2 = \pi,\\
  \left \langle 1,x  \right \rangle &= \int_{-1}^{1}
                                      \frac{x}{\sqrt{1-x^2}}\text{d}x = 0,\\
  \left \langle x,x  \right \rangle &= \left \langle 1,x^2  \right
                                      \rangle = \|T_1\|^2 =
                                      \frac{\pi}{2},\\
  \left \langle x,x^2  \right \rangle &= \int_{-1}^{1}
                                      \frac{x^3}{\sqrt{1-x^2}}\text{d}x
                                        = 0,\\
  \left \langle x^2,x^2  \right \rangle &= \int_{-1}^{1}
                                      \frac{x^4}{\sqrt{1-x^2}}\text{d}x = \frac{3}{8}\pi,\\
\end{align*}
where the last equation comes from the fact that
\begin{align*}
  \|T_2\|^2 = \int_{-1}^{1}\frac{4x^4 - 4x^2 +
  1}{\sqrt{1-x^2}}\text{d}x = \frac{\pi}{2}.
\end{align*}
and
\begin{align*}
  &\int_{-1}^{1}\frac{x^2}{\sqrt{1-x^2}}\text{d}x = \frac{\pi}{2},\\
  &\int_{-1}^{1}\frac{1}{\sqrt{1-x^2}}\text{d}x = \pi.
\end{align*}
Combining
\begin{align*}
  \left \langle 1,y  \right \rangle &= \int_{-1}^{1}
                                      1\text{d}x = 2,\\
  \left \langle x,y  \right \rangle &= \int_{-1}^{1}
                                      x\text{d}x = 0,\\
  \left \langle x^2,y  \right \rangle &= \int_{-1}^{1}
                                      x^2\text{d}x = \frac{2}{3},
\end{align*}
we get the normal equation
\begin{align*}
  \begin{bmatrix}
  \pi& 0 & \frac{\pi}{2}\\
  0& \frac{\pi}{2} &0 \\
  \frac{\pi}{2}&0 & \frac{3}{8}\pi&
\end{bmatrix}
\begin{bmatrix}
 b_0\\
 b_1\\
 b_2
\end{bmatrix}
  =
  \begin{bmatrix}
 2\\
 0\\
 \frac{2}{3}
\end{bmatrix},
\end{align*}
which implies $b_0 = \frac{10}{3\pi}, b_1 = 0, b_2 = -\frac{8}{3\pi}$.
Hence
\begin{align*}
  \varphi_2 = -\frac{8}{3\pi}x^2 + \frac{10}{3\pi}.
\end{align*}
    
  \end{enumerate}
  
\item
  % 问题4
  \textbf{Solution}\par
  \begin{enumerate}
  \item
    We use $\sum$ to represent $\sum_{i=1}^{N}$ in this problem for convenience.\\
$v_0 = u_0 = 1$, $\|v_0\|^2 = \sum 1 = 12$, $u_0^* =
\sqrt{\frac{1}{12}}$.\\
$u_1 = x$,
\begin{align*}
  v_1 &= u_1 - \left \langle u_1,u_0^*  \right \rangle u_0^*\\
  &= x - \left \langle x,\sqrt{\frac{1}{12}} \right \rangle
    \sqrt{\frac{1}{12}}\\
  &= x - \frac{1}{12}\sum x = x - \frac{13}{2}.
\end{align*}
\begin{align*}
  \|v_1\|^2 &= \sum (x - \frac{13}{2})^2 = 143,\\
  u_1^* &= \sqrt{\frac{1}{143}}(x - \frac{13}{2}).
\end{align*}
$u_2 = x^2$,
\begin{align*}
  v_2 &= u_2 - \left \langle u_2,u_1^*  \right \rangle u_1^* - \left \langle u_2,u_0^*  \right \rangle u_0^*\\
  &= x^2 - \left \langle x^2,\sqrt{\frac{1}{143}}(x - \frac{13}{2})
    \right \rangle \sqrt{\frac{1}{143}}(x - \frac{13}{2}) - \left \langle x^2,\sqrt{\frac{1}{12}} \right \rangle
    \sqrt{\frac{1}{12}}\\
      &= x - \frac{1}{143}(\sum x^2(x - \frac{13}{2}))(x - \frac{13}{2}) - \frac{1}{12}\sum
    x^2 \\
  &= x^2 - 13x + \frac{91}{3}.
\end{align*}
\begin{align*}
\|v_2\|^2 &= \sum (x^2 - 13x + \frac{91}{3})^2 =
  \frac{4004}{3},\\
  u_2^* &= \sqrt{\frac{3}{4003}}(x^2 - 13x + \frac{91}{3}). \\  
\end{align*}
Hence
\begin{align*}
  u_0^* &=
  \sqrt{\frac{1}{12}},u_1^* = \sqrt{\frac{1}{143}}(x - \frac{13}{2}),\\
  u_2^* &= \sqrt{\frac{3}{4004}}(x^2 - 13x + \frac{91}{3}).
\end{align*}
\item
  With $u_0^*,u_1^*,u_2^*$ in Question 2, we compute that
\begin{align*}
  b_0 = \left \langle y,u_0^*  \right \rangle &=
                                                \sqrt{\frac{1}{12}}\sum
                                                y = \frac{1662}{\sqrt{12}}
                                          ,\\
  b_1 = \left \langle y,u_1^*  \right \rangle &= \sqrt{\frac{1}{\sqrt{143}}}\sum y(x - \frac{13}{2})=\frac{589}{\sqrt{143}},\\
  b_2 = \left \langle y,u_2^*  \right \rangle &=
                                                \sqrt{\frac{3}{4004}}\sum
                                                y(x^2 - 13x +
                                                \frac{91}{3})\\
  &=12068\sqrt{\frac{3}{4004}}.
\end{align*}
Hence
\begin{align*}
  \hat{\varphi} &=  b_0 u_0^* + b_1 u_1^* + b_2 u_2^*\\
  &=
    \frac{1662}{\sqrt{12}}\sqrt{\frac{1}{12}}+\frac{589}{\sqrt{143}}\sqrt{\frac{1}{143}}(x
    -
    \frac{13}{2})\\
  &+12068\sqrt{\frac{3}{4004}}\sqrt{\frac{3}{4004}}(x^2
    - 13x + \frac{91}{3})\\
  &=9.042x^2 - 113.427x + 386.000,
\end{align*}
which is the same as the result in Example 5.48.
  \item
    The method using normal equation can be reused, since the matrix
$G(1,x,x^2)$ stay the same when $y_i$'s are different. The method
using orthonormal polynomials can also be reused, since the basis
$u_0^*,u_1^*,u_2^*$ stay the same when $y_i$'s are different. However,
the method using orthonormal polynomials has no need to solve linear
equations and has better condition number. So it has advantages over
the one using normal equation in this case.
  \end{enumerate}
  
  
\end{enumerate}
\newpage

\section{Programming assignments}
\begin{enumerate}
\item %A
  The result is as following:
  \begin{equation*}
    f(x) = -0.23844x^2 + 2.6704x + 2.1757.
  \end{equation*}
  The plot is shown in Fig\ref{fig1}.
  \begin{figure}[H]
    \includegraphics[width=1.000\textwidth]{homework5/A.png}
    \caption{Discrete least square plot}
    \label{fig1}
  \end{figure}

\item %B
  The result is as following:
  \begin{equation*}
    f(x) = -0.23844x^2 + 2.6704x + 2.1757.
  \end{equation*}
  The condition number of $G$ is 18980.8943, while the condition number of $R_1$ is 137.7712.
  The plot is shown in Fig\ref{fig2}.
  \begin{figure}[H]
    \includegraphics[width=1.000\textwidth]{homework5/B.png}
    \caption{Discrete least square plot}
    \label{fig2}
  \end{figure}

\end{enumerate}



\end{document}
